﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions.Problems
{
    /*
     * The number 512 is interesting because it is equal to the sum of its digits raised to some power: 5 + 1 + 2 = 8, and 83 = 512. Another example of a number with this property is 614656 = 284.

We shall define an to be the nth term of this sequence and insist that a number must contain at least two digits to have a sum.

You are given that a2 = 512 and a10 = 614656.

Find a30.

     * */
    class Problem119 : IProblem
    {
        public string Calculate()
        {
            Dictionary<string, long> results = new Dictionary<string, long>();

            for (int a = 2; a < 1000; a++)
            {
                long n = a;
                for (int p = 2; p < 1000; p++)
                {
                    n *= a;
                    if (SumDigits2(n) == a)
                        results.Add(a+":"+p,n);
                }
            }

            var q = results.Values.OrderBy(x => x).ToList();

            return q[29].ToString();
        }

        public int SumDigits1(long n)
        {
            string num = n.ToString();
            int sum = 0;
            foreach (char c in num)
                sum += c - '0';
            return sum;
        }

        public int SumDigits2(long n)
        {
            int sum = 0;
            while (n > 0)
            {
                sum += (int)(n % 10);
                n /= 10;
            }
            return sum;
        }
    }
}
